#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣1443. 收集树上所有苹果的最少时间
// 【难度】中等
// 【提交】2025.10.16 https://leetcode.cn/problems/minimum-time-to-collect-all-apples-in-a-tree/submissions/671180193/
// 【标签】树；深度优先搜索
class Solution {
public:
    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
        vector<vector<int>> g(n);
        for(auto& e : edges) {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }
        return dfs(g, hasApple, 0, -1);
    }
    int dfs(vector<vector<int>>& g, vector<bool>& hasApple, int cur, int fa) {
        int res = 0;
        for(auto& child : g[cur]) {
            if(child == fa) continue;
            int child_time = dfs(g, hasApple, child, cur);
            if(child_time > 0 || hasApple[child]) {
                res += child_time + 2;
            }
        }
        return res;
    }
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定一棵由n个节点组成的树，以及一个布尔数组hasApple表示哪些节点有苹果。
 * 从节点0出发，收集所有苹果并返回起点，每条边需要花费1单位时间。
 * 求收集所有苹果所需的最少时间。
 * 模型：树形结构+深度优先搜索，通过后序遍历计算收集苹果的总时间。
 * 
 * 二、标准解法状态设计
 * 1. 根据边列表构建树的邻接表表示。
 * 2. 使用深度优先搜索遍历树结构。
 * 3. 对于每个节点，递归计算所有子树的收集时间。
 * 4. 如果子树有苹果或子树收集时间大于0，则需要访问该子树，并加上往返时间2。
 * 5. 返回从根节点开始的总收集时间。
 * 
 * 三、你的实现思路
 * 使用DFS遍历树，在递归过程中计算收集每个子树中苹果所需的时间。
 * 通过判断子树是否有苹果或子树收集时间是否大于0，决定是否需要访问该子树。
 * 
 * 四、逐行注释（带细节提醒）
 * vector<vector<int>> g(n); // 构建邻接表
 * for(auto& e : edges) { // 构建无向图
 *     g[e[0]].push_back(e[1]);
 *     g[e[1]].push_back(e[0]);
 * }
 * 
 * int dfs(vector<vector<int>>& g, vector<bool>& hasApple, int cur, int fa) {
 *     int res = 0; // 初始化当前子树总时间
 *     
 *     for(auto& child : g[cur]) { // 遍历邻居
 *         if(child == fa) continue; // 跳过父节点
 *         
 *         int child_time = dfs(g, hasApple, child, cur); // 递归计算子树时间
 *         
 *         // 如果子树需要访问（有苹果或子树时间>0）
 *         if(child_time > 0 || hasApple[child]) {
 *             res += child_time + 2; // 加上子树时间和往返时间
 *         }
 *     }
 *     return res; // 返回当前子树总时间
 * }
 * 
 * 五、正确性证明
 * 算法通过DFS遍历整棵树，对于每个节点：
 * 1. 计算所有子树的收集时间
 * 2. 如果子树有苹果或子树收集时间大于0，说明需要访问该子树
 * 3. 访问子树需要往返时间2（去1回1）
 * 4. 最终得到从根节点出发收集所有苹果的总时间
 * 由于DFS会访问所有节点，且每个节点都正确计算了子树的访问时间，因此算法正确。
 * 
 * 六、复杂度
 * 时间：O(n)，每个节点只被访问一次。
 * 空间：O(n)，需要邻接表存储树结构，递归栈深度为树的高度。
 * 
 * 七、优缺点分析
 * 优点：
 *   - 算法高效，只需一次DFS遍历；
 *   - 代码简洁，逻辑清晰；
 *   - 准确计算了往返时间，避免了重复计算。
 * 缺点：
 *   - 递归深度可能受树高度限制；
 *   - 对于大规模数据可能需要迭代DFS。
 * 
 * 八、改进建议
 * 1. 可以添加输入验证：if (n == 0) return 0;
 * 2. 可以使用迭代DFS（栈）避免递归深度问题；
 * 3. 对于教学场景，可以添加注释解释为什么往返时间是2个单位。
 * 
 * 九、一句话总结
 * 通过深度优先搜索计算子树收集时间并累加往返时间，你的实现高效地解决了收集苹果的最少时间问题，
 * 展现了树形结构问题中递归思想的实用价值。
 */